package leetcode;

import java.util.List;

/**
 * 贪心算法：划分字母区间
 */
public class Solution35 {
    class Solution {
        public List<Integer> partitionLabels(String s) {
            List<Integer> list = new LinkedList();
            int[] edge = new int[27];
            char[] chars = s.toCharArray();
            for(int i = 0; i <chars.length;i++){
                edge[chars[i] - 'a'] = i;
            }
            int left = -1;
            int right = 0;
            for(int i = 0; i < chars.length;i++){
                right = Math.max(right, edge[chars[i] - 'a']);
                if(right == i){
                    list.add(i - left);
                    left = right ;
                }
            }
            return list;
        }
    }
}
